package structure;

import java.util.ArrayList;
import java.util.List;
import node.Insertable;

/**
 *
 * @author Vojta
 */
public class Heap implements DataStructure {

    protected final int NOT_EXIST = -1;
    protected List<Insertable> array;

    public Heap() {
        array = new ArrayList<Insertable>();
    }

    public boolean add(Insertable i) {
       //if (i == null || find(i.getId()) != null) {
       //     return false;
       // }
        array.add(i);
        return true;
    }

    public Insertable delete(int id) {
        Insertable temp = find(id);
        if (temp != null) {
            array.remove(temp);
        }
        return temp;
    }

    public Insertable find(int id) {
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i).getId() == id) {
                return array.get(i);
            }
        }
        return null;
    }
    
    public int size() {
        return array.size();
    }

    public void buildHeap() {
        for (int i = array.size() / 2 + 1; i >= 0; i--) {
            heapify(i);
        }
    }

    protected void heapify(int index) {
        int largest, leftNode = getLeftNode(index), rightNode = getRightNode(index);
        if (leftNode != NOT_EXIST && array.get(index).compareTo(array.get(leftNode)) == -1) {
            largest = leftNode;
        } else {
            largest = index;
        }
        if (rightNode != NOT_EXIST && array.get(largest).compareTo(array.get(rightNode)) == -1) {
            largest = rightNode;
        }
        if (index != largest) {
            array.get(index).switchElements(array.get(largest));
            heapify(largest);
        }
    }

    protected int getLeftNode(int i) {
        return (2 * i + 1 < array.size()) ? (2 * i + 1) : NOT_EXIST;
    }

    protected  int getRightNode(int i) {
        return (2 * i + 2 < array.size()) ? (2 * i + 2) : NOT_EXIST;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.size(); i++) {
            sb = sb.append(array.get(i)).append(" ");
        }
        return sb.toString();
    }
}
